Network coding refers to data packet routing techniques that may be used instead of ‘store and forward’ networking techniques. In general, network coding is performed at network nodes to combine incoming packets into coded packets before transmitting those coded packets to a recipient node or nodes. The combination of data is such that each recipient node is able to recover the original data from less than all received packets. Network coding thus provides improved resilience to packet loss, and moreover, increases throughput for certain classes of network topologies.
More particularly, at each node, the outgoing packets contain vectors that are calculated as a linear combination of vectors conveyed by incoming packets. With random linear network coding, packets are combined using coefficients that each node chooses at random. A recipient node is able to recover the original data from any set (of sufficient cardinality) of linearly independent vectors and without prior knowledge of the coefficients chosen by the intermediate nodes. Linear network codes offer robustness, adaptability and thus offer benefits in many practical applications, e.g., in wireless and sensor networks.
However, network coding is highly sensitive to pollution attacks, in which malicious nodes inject corrupted packets (e.g., one or more packets outside of the linear span of received packets) into the network, which prevents the recipient node from recovering the original file. Because nodes perform linear transformation over the incoming nodes, even a single corrupted packet is likely to contaminate the entire network and eventually hinder the decoding process. Intermediate non-malicious nodes thus need a way to verify the validity of incoming packets and filter out the bad ones. Packets cannot be authenticated using traditional digital signature schemes, because the transmitted packets need to be modified by the network nodes and thus cannot be simply signed by the source. In sum, traditional digital signature schemes fail in situations where a digital signature on arbitrarily combined packets needs verification, assuming that the total cost of verifying independent signatures is costlier than verifying a single combined signature on a target node.